package quwei;

import java.util.Scanner;

public class Test4_5 {
    static int n;
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        System.out.println("请输入站点的个数n：");
        n=scanner.nextInt();
        System.out.println("请依次输入各站点之间的租金：");
        int[][] r=new int[n+1][n+1];                            //存放各站点之间的租金
        int[][] m=new int[n+1][n+1];                            //各个子问题的最优值
        int[][] s=new int[n+1][n+1];                            //各个子问题的最优决策
        for(int i=1;i<=n;i++) {
            for(int j=i+1;j<=n;j++) {
                r[i][j]=scanner.nextInt();
                m[i][j]=r[i][j];                                //初始化m数组
            }   
        }
        rent(m,s);                                              //求最少租金
        System.out.println("花费最少的租金为："+m[1][n]);
        System.out.print("最少租金经过的站点：1");
        print(1,n,s);
        System.out.println();
        scanner.close();
    }

    /*最少租金求解函数*/
    public static void rent(int[][] m,int[][] s) {
        int i,j,k,d;
        for(d=3;d<=n;d++) {                                     //将问题划分为小规模d，3个站点、4个站点...n个站点
            for(i=1;i<=n-d+1;i++) {                             //子问题的初始站点
                j=i+d-1;                                        //子问题的终点站点
                for(k=i+1;k<j;k++) {                            //可停靠站点
                    int temp=m[i][k]+m[k][j];                   //在站点k停留
                    if(temp<m[i][j]) {                          //停留后的租金和比直达的租金便宜
                        m[i][j]=temp;
                        s[i][j]=k;                              //记录停靠点
                    }
                }
            }       
        }
    }

    /*求得停靠点，当s[i][j]=0时说明中间没有停靠点，输出站点j，否则划分为两个子问题*/
    public static void print(int i,int j,int[][] s) {
        if(s[i][j]==0) {
            System.out.print("——"+j);
            return;
        }
        print(i,s[i][j],s);
        print(s[i][j],j,s);
    }
}
